#include "stack_queue.h"
using namespace std;
listNode::listNode(int nodeData, listNode* succ){
    data = nodeData;
    next = succ;
}

MyStack::MyStack(){
    topNode = NULL;
    stackSize = 0;
}

MyStack::~MyStack(){
    int a;
    while(stackSize > 0)pop(a);
    delete topNode;
}

MyQueue::MyQueue(const int& c){
    capacity = c;
    queue = new int[c];
    front = 0;
    rear = 0;
}

MyQueue::~MyQueue(){
    delete []queue;
}

bool MyQueue::enQueue(const int& a){
    if((rear - front + capacity + 1)%capacity == 0)return 0;
    queue[rear] = a;
    rear = (rear + 1) % capacity;
    return 1;
}

bool MyQueue::deQueue(int& a){
    if(rear == front)return 0;
    a = queue[front];
    front = (front + 1) % capacity;
    return 1;
}

bool MyQueue::getFront(int& a){
    if(rear == front)return 0;
    a = queue[front];
    return 1;
}

void MyStack::printStack(){
    listNode* p = topNode;

    while(p != NULL){
        if(p->next == NULL)
            cout << p->data << endl;
        else
            cout << p->data << ",";

        p = p->next;

    }
}

void MyQueue::printQueue(){
    int cursor = front;

    while(cursor != rear)
    {
        if((cursor + 1) % capacity == rear)
            cout << queue[cursor] << endl;
        else
            cout << queue[cursor] << ",";

        cursor = (cursor + 1) % capacity;
    }
}
bool MyStack::push(const int& data1){
    listNode* a = new listNode;
    if(a==NULL)return 0;
    listNode* temp = topNode;
    topNode = a;
    topNode->data = data1;
    topNode->next = temp;
    stackSize++;
    return 1;
}
int MyStack::getSize(){
    return stackSize;

}

bool MyStack::pop(int& a){
    if(stackSize<=0)return 0;
    a = topNode->data;
    listNode* temp = topNode;
    topNode = topNode->next;
    delete temp;
    stackSize--;
    return 1;
}

bool MyStack::getTop(int& a){
    if(stackSize<=0)return 0;
    a = topNode->data;
    return 1;
}

bool MyStack::empty(){
    if(stackSize<=0)return 1;
    return 0;
}

bool postfixExpression(const string& des, string& result){
    int t,ch;
    int left = 0, right = 0;
    for(int i = 0;i < des.length();i++){
        if(des[i]==40)left++;
        if(des[i]==41)right++;
    }

    if(left != right){
        result = "Expression is wrong!";
        return false;
    }

    MyStack res;
    MyStack thr;

    for(int i = 0;i < des.length();i++){

    ch = des[i];

        switch(ch){

    case 40:    // ( -6
        thr.push(-6);
        break;

    case 41:    // ) -5

        thr.getTop(t);
        while(t != -6){
            thr.pop(t);
            res.push(t);
            thr.getTop(t);
}
              thr.pop(t);
        break;


    case 42:    // * -1
        if(thr.empty()){thr.push(-1);
break;}
            thr.getTop(t);
        while(-1 < t&&!thr.empty()){
            thr.pop(t);
            res.push(t);
        }
        thr.push(-1);
        break;

    case 43:    // + -3
        if(thr.empty()){thr.push(-3);
break;}
            thr.getTop(t);
        while(-3 < t&&!thr.empty()){
            thr.pop(t);
            res.push(t);
        }
        thr.push(-3);
        break;
    case 45:    // - -4
        if(thr.empty()){thr.push(-4);
break;}
            thr.getTop(t);
        while(-4 < t&&!thr.empty()){
            thr.pop(t);
            res.push(t);
        }
        thr.push(-4);
        break;

    case 47:    // / -2
        if(thr.empty()){thr.push(-2);
break;}
            thr.getTop(t);
        while(-2 < t&&!thr.empty()){
            thr.pop(t);
            res.push(t);
        }
        thr.push(-2);
        break;

    default:    // 0~9
        res.push(ch-'0');
        break;

}


}
    MyStack reres;
    while(!thr.empty()){
        thr.pop(t);
        res.push(t);
    }

    while(!res.empty()){
        res.pop(t);
        reres.push(t);
    }
    while(!reres.empty()){
        reres.pop(t);
        switch(t){
    case -1:
        result+='*';
        break;
    case -2:
        result+='/';
        break;
    case -3:
        result+='+';
        break;
    case -4:
        result+='-';
        break;
    default:
        result+=t+'0';
        break;
        }
    }
    return true;
}

bool expressionVal(const string& des, int& result){
    int t,ch;
    int left = 0, right = 0;
    for(int i = 0;i < des.length();i++){
        if(des[i]==40)left++;
        if(des[i]==41)right++;
    }

    if(left != right)return false;

    MyStack res;
    MyStack thr;

    for(int i = 0;i < des.length();i++){

    ch = des[i];

        switch(ch){

    case 40:    // ( -6
        thr.push(-6);
        break;

    case 41:    // ) -5

        thr.getTop(t);
        while(t != -6){
            thr.pop(t);
            res.push(t);
            thr.getTop(t);
}
              thr.pop(t);
        break;


    case 42:    // * -1
        if(thr.empty()){thr.push(-1);
break;}
            thr.getTop(t);
        while(-1 < t&&!thr.empty()){
            thr.pop(t);
            res.push(t);
        }
        thr.push(-1);
        break;

    case 43:    // + -3
        if(thr.empty()){thr.push(-3);
break;}
            thr.getTop(t);
        while(-3 < t&&!thr.empty()){
            thr.pop(t);
            res.push(t);
        }
        thr.push(-3);
        break;
    case 45:    // - -4
        if(thr.empty()){thr.push(-4);
break;}
            thr.getTop(t);
        while(-4 < t&&!thr.empty()){
            thr.pop(t);
            res.push(t);
        }
        thr.push(-4);
        break;

    case 47:    // / -2
        if(thr.empty()){thr.push(-2);
break;}
            thr.getTop(t);
        while(-2 < t&&!thr.empty()){
            thr.pop(t);
            res.push(t);
        }
        thr.push(-2);
        break;

    default:    // 0~9
        res.push(ch-'0');
        break;

}


}
    while(!thr.empty()){
        thr.pop(t);
        res.push(t);
    }
MyStack reres;
    while(!res.empty()){
        res.pop(t);
        reres.push(t);
    }
    reres.pop(t);
    res.push(t);
    int shu1,shu2;
    while(!reres.empty()){
        reres.pop(t);
        if(t>=0)res.push(t);
        if(t<0){
            res.pop(shu1);
            res.pop(shu2);
            switch(t){
        case -1:
            res.push(shu1*shu2);
            break;
        case -2:
            if(!shu1){result = 0;return 0;}
            res.push(shu2/shu1);
            break;
        case -3:
            res.push(shu1+shu2);
            break;
        case -4:
            res.push(shu2-shu1);
            break;
            }

        }

    }
    res.getTop(result);
    return true;
}

void yanghui(const int& n){
     MyQueue q(n*n);
 q.enQueue (1);  q.enQueue (1);
int s = 0;
for ( int i=1; i<=n; i++ ) {
cout << endl;
 q.enQueue (0);
 for ( int j=1; j<=i+2; j++ ) {
int t;
q.deQueue (t);
q.enQueue ( s+t );
s = t;
 if ( j < i+1 )
cout << s << ',';
    else if(j < i+2 )
        cout << s;
}
}
}
